<?php

require_once('DLLists.php');

abstract class Tree {
	/**
	 * 
	 * @var TreeNode
	 */
	protected $root;
	
	public function path_to($k1, $k2 = null){
		
		if ($k2 == null) {
			$to = $k1;
		} else {
			$from = $k1;
			$to = $k2;
		}
		
		
		$path = new Stack();
		$this->compute_path_to($this->root, $to, $path);
		
		return $path;
	}
	
	/**
	 * 
	 * @param TreeNode $node
	 * @param unknown $to
	 * @param Stack $path
	 */
	private function compute_path_to($node, $to, &$path) {
		
		if ($node == null) return false;
		
		if ($this->equalKey($node->getKey(), $to)) {
			$path->push($node->value);
			return true;
		}
		$found = false;
		foreach ($node->children as $child) {
			$found = $this->compute_path_to($child, $to, $path);
			if ($found) {
				$path->push($node->value);
				break;
			}
		}
		return $found;
		
	}
	
	/**
	 * 
	 * @param TreeNode $node
	 */

	
	public function equalKey($k1, $k2){
		return ($k1 == $k2);
	}
	
}

Interface IF_SearchTree {

    public function equals($node1, $node2);
    public function gt($node1, $node2);
    public function lt($node1, $node2);
    public function eq($node1, $node2);
    public function egt($node1, $node2);
    public function elt($node1, $node2);
    
}


abstract class TreeNode {
    
    public $value;
    public $children = array();
    
    public function __construct ($v) {
        $this->value = $v;
    }
    
    public function printacazz($lev = 0, $nc='-') {
        for($i=0; $i< $lev; $i++) {
            echo "---";
        }
        echo $this->toString().'<br>';
        foreach ($this->children as $nc=>$c) {
            if ($c != null)
                $c->printacazz($lev+1, $nc);
        }
    }    
    
    public function toString() {
    	return $this->value;
    }
    
    public function getKey() {
    	return $this->value;
    }    
    
}

class BSTNode extends TreeNode{
    public function __construct ($v) {
        $this->value = $v;
        $this->children = array (null,null);
    }
    
    public function &left_child() {
        return $this->children[0];
    }

    public function left_child_value() {
        return $this->children[0];
    }
    
    public function &right_child() {
        return $this->children[1];
    }    
    
    public function right_child_value() {
        return $this->children[1];
    }    
}

class AVLNode extends BSTNode {
    public $height = 1;
    public $cb = 0;
}


abstract class SearchTree extends Tree implements IF_SearchTree{
    

    /**
     * 
     * @var BSTNode
     */
    protected $root;
    /**
     *
     * @param SearchTreeNode $node
     */    
    public function __construct($value = null) {
        if ($value) {
            $this->root = new BSTNode($value);
        } else {
            $this->root = null;
        }
    }
    
    public abstract function equals($node1, $node2);
    public function gt($node1, $node2) {
        return ($this->equals($node1, $node2) == 1);
    }
    public function lt($node1, $node2) {
        return ($this->equals($node1, $node2) == -1);
    }
    public function eq($node1, $node2) {
        return ($this->equals($node1, $node2) == 0);
    }
    public function egt($node1, $node2) {
        return ($this->equals($node1, $node2) > -1);
    }
    public function elt($node1, $node2) {
        return ($this->equals($node1, $node2) < 1);
    }
    
    public function techo() {
        if ($this->root != null) {
            $this->root->printacazz(0);
        }
    }


    
}


class AVLTree extends SearchTree {
    
    private $equals_fun;
    
    public function __construct($eq_fun = null) {
        parent::__construct();
        if ($eq_fun) {
            $this->equals_fun = $eq_fun;
        } else {
            $this->equals_fun = "strnatcmp";
        }
    }
    
    public function equals($node1, $node2) {
        
        $eq = $this->equals_fun;
        
        return ($eq($node1->value, $node2->value));
    }
    
    public function insert($value) {
        $this->insert_recursive($this->root, new AVLNode($value));
    }
    /**
     * 
     * @param AVLNode $node
     * @param AVLNode $newNode
     */
    private function insert_recursive(&$node, &$newNode) {
        if ($node == null) {
            $node = $newNode;
        } else {
            if ($this->gt($newNode, $node)) {
                $this->insert_recursive($node->right_child(), $newNode);
            } else {
               $this->insert_recursive($node->left_child(), $newNode);
            }
            
            $this->updatecbh($node);
            $this->balance($node);
        }
    }
    
    /**
     *
     * @param AVLNode $node
     */
    public function rightRotation(&$node) {
        
        
        $lc = $node->left_child();
        
        $node->children[0] = $lc->children[1];
        $lc->children[1] = $node;
        $node = $lc;
        
        $this->updatecbh($lc->children[1]);
        $this->updatecbh($node);
        
    
    }
    
    public function leftRotation(&$node) {
    
        $rc = $node->right_child();
    
        $node->children[1] = $rc->children[0];
        $rc->children[0] = $node;
        $node = $rc;
    
        $this->updatecbh($rc->children[0]);
        $this->updatecbh($node);
    
    }    
    
    /**
     *
     * @param AVLNode $node
     */
    public function updatecbh(&$node) {
    
        $lh = ($node->left_child()  == null? 0 : $node->left_child()->height );
        $rh = ($node->right_child() == null? 0 : $node->right_child()->height );
    
        $node->height = 1 + max($lh,$rh);
        $node->cb = $rh - $lh;
    
    }
    /**
     * 
     * @param AVLNode $node
     */
    public function balance(&$node) {
        
        if ($node->cb == -2) {
            if ($node->left_child_value() != null && $node->left_child_value()->cb == 1) {
                $this->leftRotation($node->left_child()); 
            }
            $this->rightRotation($node);
        }
        
        if ($node->cb == 2) {
            if ($node->right_child_value() != null && $node->right_child_value()->cb == -1) {
                $this->rightRotation($node->right_child());
            }
            $this->leftRotation($node);

        }        
        
    }
    

    public function intabella() {
        $valori = array();
        $maxh = $this->root->height;
    
        $this->fill_values_at($valori, $this->root,0,0,$maxh-1);
        
        echo "-------<br><table border=1>";
            foreach ($valori as $lev => $values) {
                echo "<tr>";
                    foreach ($values as $v) {
                        $span = pow(2,$maxh-$lev);
                        echo "<td colspan=$span align=center width=20>$v</td>";
                    }
                echo "</tr>";
            }
        echo "</table>";
    
    }   

    public function fill_values_at(&$valori, $node, $lev,$index, $maxLev) {
        
        if ($lev > $maxLev) return;
        
        if ($node == null) {
            $this->put_stars($valori,$lev,$index,$maxLev);
            return;
        }
        
        
        $valori[$lev][$index] = $node->value."(".$node->height.','.$node->cb.")";
        $this->fill_values_at($valori, $node->left_child(),$lev+1,2*$index,$maxLev);
        $this->fill_values_at($valori, $node->right_child(),$lev+1,2*$index+1,$maxLev);
    }
    
    public function put_stars(&$valori, $lev,$index,$maxLev) {
        
        if ($lev > $maxLev) return;
        
        $valori[$lev][$index] = '*';
        $this->put_stars($valori, $lev+1, 2*$index,$maxLev);
        $this->put_stars($valori, $lev+1, 2*$index+1,$maxLev);        
        
    }
}


class ParentalNode extends TreeNode {
	
	public function toString() {
		return $this->value['id'];
	}
}

class ParentalTree extends Tree {
	/**
	 * 
	 * @var ParentalNode
	 */
	public $root;
	
	public $nodes = array();
	
	private $iid;
	private $pid; 
	
	public function __construct($data_set = array(), $id_index = 'id', $parent_index='parent') {
		
		$this->iid = $id_index;
		$this->pid = $parent_index;
		$this->root = new ParentalNode(array($id_index => '0', $parent_index => ''));
		
		$nodes = array();
		foreach ($data_set as $v) {
			$this->nodes[$v[$this->iid]] = new ParentalNode($v);
			if ($v[$this->pid] == null || $v[$this->pid] == '') {
				$this->root->children[] = &$this->nodes[$v[$this->iid]];
			}			
		}
		
		foreach ($data_set as $v) {
			if ($v[$this->pid] != null || $v[$this->pid] != '') {
				$this->nodes[$v[$this->pid]]->children[] = &$this->nodes[$v[$this->iid]];
			}
		}		
	}
	
	public function printacazz() {
		foreach ($this->root->children as $nodo) {
			$nodo->printacazz();
		}
	}
	
	public function intabella() {
		
	}
	
	public function insert($v) {
		$new_node = new ParentalNode($v);
		
		if (isset($this->nodes[$v[$this->iid]])) {
			$new_node->children = $this->nodes[$v[$this->iid]]->children;		
		} 
		$this->nodes[$v[$this->iid]] = &$new_node;
		
		if ($v[$this->pid] != null && $v[$this->pid] != '') {
			$this->nodes[$v[$this->pid]]->children[] = &$this->nodes[$v[$this->iid]];
		} else {
			$this->root->children[] = &$this->nodes[$v[$this->iid]];
		}
	}
	
	public function children_of($pid) {
		$result = array();
		
		$result[] = $this->nodes[$pid]->value;

		foreach ($this->nodes[$pid]->children as $child) {
			$this->children_of_rec($child, $result);
		}
		
		return $result;
	}
	
	private function children_of_rec($node, &$result) {
		if ($node == null) return;
		$result[] = $node->value;
		foreach ($node->children as $child) {
			$this->children_of_rec($child, $result);
		}		
	}
	
}

/*
class MapTree extends AVLTree {
    
    public $key;

    public function equals($node1, $node2)) {
        return strnatcmp($this->key, $tree->key);
    }
} */